package 动态规划;

/**
 * 升级版
 * 给定一个数组，不能取两个下标相邻的元素，求能取出的最大值
 * 例如{1,3,5,7,5};要么取1，5，5 要么取3,7
 * 给题目加一个条件，头和尾部是相邻的 即取头不能取尾
 */
public class Ch04_打家劫舍版本2 {
    public static void main(String[] args) {
        int[] nums={0,0};
        int res=Math.max(maxMoney(nums, 0, nums.length-1),maxMoney(nums, 1, nums.length));
        System.out.println(res);
    }

    public static int maxMoney(int[] nums,int start,int end){
        if (nums==null||nums.length==0){
            return 0;
        }
        if (nums.length<2){
            return nums[0];
        }
        if (nums.length==2){
            return nums[0]>nums[1]?nums[0]:nums[1];
        }
        int[] dp=new int[3];
        //dp[0]表示待求结果的上 上 一个
        dp[0]=nums[start];

        dp[1]=Math.max(dp[0],nums[start+1]);

        for (int i=start+2;i<end;i++){
//          dp[2]是待求结果的那个
            dp[2]=Math.max(dp[1],dp[0]+nums[i]);    //f(n)
            dp[0]=dp[1];    //dp[0]是待求结果的 上 上 一个。这一步是将 上一个结果移到 上 上 一个 结果
            dp[1]=dp[2];    //dp[1]是带求结果的 上一个。  这一步是将当前结果移到 上一个结果
        }
        return dp[1];   //返回dp[1]因为 我们最后会将结果移入到dp[1]
    }
}
